11602 카드게임

TL;DR

DP[i][j] : i~j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수를 저장한다.

상대 플레이어도 같은 DP배열을 사용한다.

문제 특성상, 플레이어가 모든 카드를 반반 갈라먹기 때문에 (카드 개수가 홀수라면 근우가 하나 더 챙김) DP[i][j]에 대하여 cards[i:j].sum() - DP[i][j] 하면 턴 상관 없이 상대플레이어의 점수를 알 수 있다. 이 점을 착안하여 점화식을 세울 수 있다. 진짜 DP인지도 몰랐는데...

DP[k, j] = max(c[k] + c[k+1 : j].sum() - DP[k+1, j],
			   c[j] + c[k : j-1].sum() - DP[k, j-1])